package main

import "sync"

//链表队列
//队列是先进先出，和栈操作顺序相反
type LinkQueue struct {
	root *LinkNode  //链表起点
	size int        //队列元素数量
	lock sync.Mutex // 并发安全锁
}

//链表节点
type LinkNode struct {
	Next  *LinkNode
	value string
}

// 入队
func (queue *LinkQueue) Add(v string) {
	queue.lock.Lock()
	defer queue.lock.Unlock()
	// 如果栈顶为空 那么增加节点
	if queue.root == nil {
		queue.root = new(LinkNode)
		queue.root.value = v
	} else {
		//否则新元素插入链表的末尾
		newNode := new(LinkNode)
		newNode.value = v
		// 一直遍历到链表尾部
		nowNode := queue.root
		for nowNode.Next != nil {
			nowNode = nowNode.Next
		}
		//新节点放在链表尾部
		nowNode.Next = newNode
	}
	//队中元素数量+1
	queue.size = queue.size + 1

}

func (queue *LinkQueue) Remove() string {
	queue.lock.Lock()
	defer queue.lock.Unlock()

	//队中元素已空
	if queue.size == 0 {
		panic("empty")
	}

	//顶部元素要出队
	topNode := queue.root
	v := topNode.value

	//将顶部元素的后继链接链上
	queue.root = topNode.Next

	//队列中元素数量-1
	queue.size = queue.size - 1
	return v
}
